#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 链表节点定义
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 最小堆实现合并k个升序链表
class Solution 
{
public:
    // 自定义比较器，用于最小堆
    struct Compare 
    {
        bool operator()(ListNode* a, ListNode* b) 
        {
            return a->val > b->val;  // 最小堆需要大于号
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        // 先int n = size 好像也还可以
        if (lists.empty()) 
            return nullptr;
        
        // 创建最小堆，存储链表节点指针
        priority_queue<ListNode*,vector<ListNode*>,Compare> minHeap;
        
        // 将所有链表的头节点加入最小堆
        for (ListNode* list : lists) 
        {
            if (list) 
            {
                minHeap.push(list);
            }
        }
        
        // 创建哑节点简化操作 (这是哑节点)
        ListNode dummy(0);  // 在内存中new了一个节点
        ListNode* current = &dummy;
        
        // 为什么不创建 *dummy 然后直接复制一份
        // 不断从堆中取出最小节点
        while (!minHeap.empty()) 
        {
            // 取出当前最小节点
            ListNode* minNode = minHeap.top();
            minHeap.pop();
            
            // 将最小节点连接到结果链表
            current->next = minNode;
            current = current->next;
            
            // 没有见过这样的思想
            // 如果该节点还有后续节点，将后续节点加入堆中
            if (minNode->next != nullptr) 
            {
                minHeap.push(minNode->next);
            }
        }
        
        // 返回哑节点的next 即头节点
        return dummy.next;
    }
};

// 好简单

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) 
{
    ListNode dummy(0);
    ListNode* current = &dummy;
    for (int num : nums) 
    {
        current->next = new ListNode(num);
        current = current->next;
    }
    return dummy.next;
}

// 辅助函数：打印链表
void printList(ListNode* head) 
{
    while (head != nullptr) 
    {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 测试代码
int main() 
{
    Solution solution;
    
    // 创建测试链表
    vector<ListNode*> lists;
    lists.push_back(createList({1, 4, 5}));
    lists.push_back(createList({1, 3, 4}));
    lists.push_back(createList({2, 6}));
    
    cout << "输入链表:" << endl;
    for (int i = 0; i < lists.size(); i++) 
    {
        cout << "链表" << i + 1 << ": ";
        printList(lists[i]);
    }
    
    // 合并链表
    ListNode* result = solution.mergeKLists(lists);
    
    cout << "\n合并后的链表:" << endl;
    printList(result);
    
    return 0;
}